package leetcode.editor.cn.dsa05_annularLinkedList;
//给定一个链表，判断链表中是否有环。
public class LinkedListCycle141_1 {
    class ListNode {
        int val;
        ListNode next;
        ListNode (int x) {
            val = x;
            next = null;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法二：快慢指针解法
         * 1.定义快慢两个指针：
         *   slow=head; fast=head.next;
         * 2.遍历链表：
         *   快指针步长为2： fast=fast.next.next;
         *   慢指针步长为1： slow=slow.next;
         * 3.当且仅当快慢指针重合，有环，返回true
         * 4.快指针为null，或其next指向null，没有环，返回false
         * @param head
         * @return
         */
        public boolean hasCycle(ListNode head) {
            if (head == null) return false;
            // 1.定义快慢两个指针
            ListNode slow = head;
            ListNode fast = head.next;
            // 2.遍历链表，结束条件为快指针为null，或其next指向null
            while (fast != null && fast.next != null) {
                // 3.当且仅当快慢指针重合：有环，操作结束
                if (slow == fast) {
                    return true;
                }
                slow = slow.next; // 快指针步长为2
                fast = fast.next.next; // 慢指针步长为1
            }
            // 循环正常结束说明没有环，返回false
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}